class Solution(object):
    def kthSmallest(self, matrix, k):
        """
        :type matrix: List[List[int]]
        :type k: int
        :rtype: int
        """
        from heapq import *
        heaq = []
        rows = len(matrix)
        cols = len(matrix[0])
        for i in range(cols):
            heappush(heaq, (matrix[0][i], 0, i))
        for i in range(k-1):
            value, x, y = heappop(heaq)
            if x + 1 < rows:
                heappush(heaq, (matrix[x+1][y], x+1, y))
        return heaq[0][0]
